package top.minuy.structure.graph.representations.matrix;

import top.minuy.res.graph.GraphRes;
import top.minuy.structure.linear.array.Array;

/**
 * 邻接矩阵测试
 *
 * @author Minuy
 * @time 15:59
 * @date 2021/11/15
 */
public class Test {
    public static void main(String[] args) {
        System.out.println("图的邻接矩阵表示：");
        AdjMatrix adjMatrix = new AdjMatrix(GraphRes.ADJ_MATRIX_G_TXT);
        show(adjMatrix.adj(0));
        System.out.println(adjMatrix);


        System.out.println("图的邻接表（LinkedList）表示：");
        AdjList adjList = new AdjList(GraphRes.ADJ_MATRIX_G_TXT);
        show(adjList.adj(0));
        System.out.println(adjList);

        System.out.println("图的邻接表（TreeSet）表示：");
        AdjSet adjSet = new AdjSet(GraphRes.ADJ_MATRIX_G_TXT);
        show(adjSet.adj(0));
        System.out.println(adjSet);
    }

    static void show(Array<Integer> array){
        for (int i=0;i<array.getSize();i++){
            System.out.print(array.get(i));
            if (i!=array.getSize()-1){
                System.out.print(", ");
            }else {
                System.out.println();
            }
        }
    }
}

/*
 * 	空间复杂度	建图	查询是否相邻	查询所有邻接顶点	应用
 * 邻接矩阵	O(V²)	O(E)	O(1)	O(V)	稠密图
 * 	对于稀疏图来说太浪费空间了，而我们一般处理的是稀疏图，这是其缺点之一。	得益于数组的快速的查询速度，在查重方面速度很快，这是其优点之一。	使用数组可以直接定位所需信息，速度很快，这是其优点之一。	需要遍历当前顶点对应的整个第二维数组，而第二维数组大小为V，在稀疏图中，这是邻接矩阵的又一缺点。
 * "邻接表
 * （List）"	O(V+E)	"O(E)
 * 如果查重 O(V*E)"	"O(degree(v))
 * O(V)"	"O(degree(v))
 * O(V)"	稀疏图
 * 	使用链表来存储边，不需要额外的空间，是其优点之一。	在建图查重这一块，时间复杂度最坏为O(E),即一个顶点与其他的所有节点相连，这是其缺点之一。	在最坏的情况下，需要遍历整个链表来查询，也就是它的度，而这个度最坏的情况下为V。	取决于链表的长度，应该是顶底的度degree(v)，最差的情况下degree(v)=V,理论上只需要把这个链表返回就可以了，但是要保证不能被随意修改，所以还是要遍历一遍存到缓存数组中。基于语言语法可以在一定程度上优化这一点。
 * "邻接表
 * （TreeSet）"	O(V+E)	O(ElogV)	O(logV)	"O(degree(v))
 * O(V)"	"稀疏图
 * 返回的邻接顶点有序"
 * 	使用树来存储边，不需要额外的空间，是其优点之一。	平衡二叉树的插入时间复杂度为O(logn)。	平衡二叉树的查询时间复杂度为O(logn)。	取决于树的大小，应该是顶底的度degree(v)，最差的情况下degree(v)=V,理论上只需要把这个链表返回就可以了，但是要保证不能被随意修改，所以还是要遍历一遍存到缓存数组中。基于语言语法可以在一定程度上优化这一点。
 * "邻接表
 * （HashSet）"	O(V+E)	"O(ElogV)
 * 平均 O(E)"	"O(logV)
 * 平均 O(1)"	"O(degree(v))
 * O(V)"	稀疏图
 * 	使用哈希表来存储边，不需要额外的空间，是其优点之一。	哈希表的插入时间复杂度为O(logn)，平均为O(1)。	哈希表的查询时间复杂度为O(logn)，平均为O(1)。	取决于哈希表的大小，应该是顶底的度degree(v)，最差的情况下degree(v)=V,理论上只需要把这个链表返回就可以了，但是要保证不能被随意修改，所以还是要遍历一遍存到缓存数组中。基于语言语法可以在一定程度上优化这一点。
 */
